public class Test {
    /*
    题目1：验证回文串
     */
    public boolean digitAndAlpha(char x){
        if(x >= 'a' && x <= 'z' || x >= '0' && x <= '9'){
            return true;
        }
        return false;
    }

    public boolean isPalindrome(String ss) {
        String ss1 = ss.toLowerCase();
        char[] s = ss1.toCharArray();
        int n = s.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            while(left < right && !digitAndAlpha(s[left])){
                left++;
            }

            while(left < right && !digitAndAlpha(s[right])){
                right--;;
            }

            if(s[left] == s[right]){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }

    /*
    题目2：反转字符串Ⅱ
     */
    public void swap(char[] arr, int left, int right){
        while(left < right){
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    public String reverseStr(String ss, int k) {
        char[] s = ss.toCharArray();
        int n = s.length;

        for(int i = 0; i < n; i += 2 * k){
            swap(s, i, Math.min(i + k, n) - 1);
        }

        return new String(s);
    }

    /*
    题目3：验证回文串Ⅱ
     */
    public boolean subValidPalindrome(char[] arr, int left, int right){
        while(left < right){
            if(arr[left] == arr[right]){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }

    public boolean validPalindrome(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            if(s[left] == s[right]){
                left++;
                right--;
            }else{
                return subValidPalindrome(s, left + 1, right) || subValidPalindrome(s, left, right - 1);
            }
        }
        return true;
    }

    /*
    题目4：反转字符串中的元音字母
     */
    public String reverseVowels(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;

        int left = 0;
        int right = n - 1;

        while(left < right){
            while(left < right && !isVowel(s[left])){
                left++;
            }

            while(left < right && !isVowel(s[right])){
                right--;
            }

            if(left < right){
                swap1(s, left, right);
                left++;
                right--;
            }
        }
        return new String(s);
    }

    // 这里用的比较巧妙！
    public boolean isVowel(char x){
        return "aeiouAEIOU".indexOf(x) >= 0;
    }

    public void swap1(char[] arr, int i, int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /*
    题目 5：下一个排列
     */
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2; // i 从倒数第二个开始
        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }

        if(i >= 0){
            int j = nums.length - 1; // j 从最后一个开始
            while(j >= 0 && nums[i] >= nums[j]){
                j--;
            }
            swap(nums, i, j);
        }

        reverse(nums,i + 1);
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start){
        int end = nums.length - 1;

        while(start < end){
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    /*
    题目 6：
     */
    
}
